This invention relates to a method of performing image transformation such as enlargement, reduction, and rotation on a rectangular image, and to a device for carrying out this method.
The need to perform such image transformations arises frequently in fields such as computer graphics, computeraided design, and desktop publishing. Such transformations are used, for example, to display letters, symbols, and other images in arbitrary sizes and orientations. Mathematically, these transformations belong to the class of affine transformations, and can be executed in a straightforward manner by matrix multiplication.
Matrix multiplication is a computationally slow process, however, so it is desirable to execute the transformation by a faster method. Faster methods can be achieved by employing well-known digital differential analyzer (DDA) algorithms.
The prior art regarding application of DDA algorithms to these transformations has been described in, for example, a Technical Paper of the Institute of Electronics and Communication Engineers of Japan (Vol. 83, No. 195, EC83-34, Nov. 24, 1983) explaining the processing method of the MN8614 Image Processor.
The prior art disclosed in this reference operates on a source image comprising a rectangular array of pixels, generating a destination image also comprising an array of pixels. The prior art can be summarized as follows.
For a reduction transformation, a DDA algorithm is applied to map a horizontal or vertical source line of M pixels onto a horizontal or vertical destination line of N pixels, where M&gt;N. The mapping is thus many-to-one, each destination pixel corresponding to one or more source pixels. When a destination pixel corresponds to more than one source pixel, the values of those source pixels are combined by OR logic to produce the value of the destination pixel. The reduction ratio is N/M.
For an enlargement transformation, the same procedure is applied in reverse, producing a one-to-many mapping of the source image onto the destination image. The value of each source pixel is transferred to one or more destination pixels.
For a rotation, the reduction procedure is applied twice to a horizontal line of source pixels to generate the x- and y-coordinates of a line of destination pixels. The reduction ratios are the cosine and sine of the angle of rotation.
Problems arise when this method is used to perform a simultaneous rotation and enlargement, however, or a simultaneous rotation and reduction. The basic reason is that the rotation transformation does not generate continuous horizontal or vertical lines of pixels, which could be correctly enlarged or reduced, but instead generates oblique lines which are not suitable for the enlargement or reduction process. The visible results are image defects such as pixel drop-outs.